package zuochengyun;

//需要排序的子数组的长度
public class NeedSortSubArrayLength {

	public int getMinLength(int[] arr){
		if(arr == null || arr.length <= 2){
			return 0;
		}
		//最小的元素
		int min = arr[arr.length - 1];
		//从右向左遍历的时候，minIndex是需要排序的最左元素的位置
		int minIndex = -1;
		for (int i = arr.length - 2; i >= 0; i--) {
			if(arr[i] > min){
				//如果arr[i] > min, 那么更新minIndex
				minIndex = i;
			}else{
				min = Math.min(min, arr[i]);
			}
		}
		//如果minIndex等于-1， 那么说明是有序的，可以直接返回
		if(minIndex == -1){
			return 0;
		}
		
		//记录左侧出现的最大值
		int max = arr[0];
		//从左向右遍历的时候，minIndex是需要排序的最左元素的位置
		int maxIndex = -1;
		for (int i = 1; i < arr.length; i++) {
			//arr[i]小于max, 那么说明需要移至左侧形成排序
			if(arr[i] < max){
				//如果arr[i] < max, 那么更新maxIndex
				maxIndex = i;
			}else{
				max = Math.max(max, arr[i]);
			}
		}
		
		return maxIndex - minIndex;
	}
}
